1. Field of the Invention
This invention relates to a data interpolating method and, more particularly, to an interpolating method which uses four consecutive items of data to interpolate (2.sup.n-1) number of interpolation points between two items of data intermediate the four items of data.
2. Description of the Related Art
In a compact disk, an analog signal is converted into digital data, and the resulting digital data is recorded on the disk. At playback, predetermined processing is applied to the digital data by a signal processor, the digital data is converted into an analog signal, and the original sound is reproduced from the analog signal. In a compact disk of this kind, there is a limit upon the degree to which the sampling interval of data acquisition can be shortened owing to limitations imposed by the speed of the A/D conversion and the amount of memory capacity. Accordingly, when a waveform which varies at a high speed is played back by being A/D-converted as is at the sampling interval which prevailed at input, a high-quality sound cannot be reproduced if the number of items of data is small. This makes it necessary to obtain a large number of points, in addition to the sampling points, by an interpolating method or the like.
A widely employed indirect interpolating method using a spline function requires a great amount of computation time and therefore is not suited to real-time processing and is inappropriate for processing used to reproduce a musical signal, which demands high speed processing.
In computer graphics, a condition of mathematical continuity is important, and obtaining visually natural pictorial data with regard to discrete pixels is a major problem. Primarily, interpolation does not play a leading role in computer graphics but serves as an aid for displaying images in fine detail. Accordingly, indirect interpolation, in which a prescribed orthogonal function is decided and then interpolated values are found, as in conventional interpolation, can be considered an ideal technique.
When a curve is displayed by indirect interpolation using a polynomial or Fourier series, there are instances where an unnatural curve is displayed owing to an oscillation phenomenon caused by deflection. Further, with indirect interpolation using a spline function, an unnatural overshoot can occur depending upon the data. In order to improve upon this, osculatory interpolation has been proposed by Ackland. However, this method of interpolation involves prolonged computation time, and some oscillation is produced as well. In a technical paper (Journal of the Association for Computing Machinery, Vol.17, No.4, October 1970, pp.589-602), Akima proposes a method of interpolation in which polynomial coefficients are decided locally, thereby making it possible to obtain visually natural results with almost no occurrence of oscillation. However, the Akima method necessitates floating-point arithmetic and therefore requires a long computation time.
In view of the foregoing, there is a need for a highly accurate method of interpolation which allows high-speed processing, and in which oscillation does not occur.
When a curve drawn on an XY plane is represented parametrically, we have X=F(m), Y=G(m). When a curve drawn in XYZ space is represented parametrically, we have X=F(m), Y=G(m), Z=H(m), where m is a parameter. Items of data generated in a computer or items of discrete data such as actually measured values are arranged in a row in regular order to construct a sequence of points {x.sub.i, g(x.sub.i)} (i=1, 2, . . . , n). When a parametric display method is applied to such a point sequence, an arbitrary point sequence is converted into a set of single-valued point sequences. Therefore, assume that {x.sub.i, g(x.sub.i)} is single-valued, without any loss of generality. Accordingly, known data g(x.sub.i) corresponds to each point x.sub.i. Let the interval .DELTA..sub.i =[x.sub.i, x.sub.i+1 ] (i=1, 2, . . . , n-1) be the interpolation interval, and let P.sub.i represent any point in the interpolation interval .DELTA..sub.i. When g(x.sub.i) (i= 1, 2, . . . , n) has been given, an interpolated value f(P.sub.i) at the point P.sub.i is obtained. This process is referred to as interpolation or curve creation.
Techniques for determining interpolated values may be classified into direct interpolation and indirect interpolation. In case of direct interpolation, an interpolated value can be computed directly based upon data at a known point in the proximity of the point to be interpolated. Since an interpolated value is determined based upon data in a local area without relation to the global circumstances, it is possible to carry out parallel arithmetic as well.
When indirect interpolation is used, an interpolated value is decided in two steps. First, a polynomial coefficient of a curve passing through a known point is calculated. Next, the coordinates of an interpolated point are substituted into a function that has been decided, and the interpolated value is determined. Since it is difficult to decide a polynomial coefficient locally, this method of interpolation is not suited to parallel arithmetic.
In indirect interpolation, m-number of parameters .phi..sub.i (i=1, 2, . . . , n) are determined based upon known data g(x.sub.i) (i=1, 2, . . . , n), where .phi..sub.i is the coefficient of each term of an interpolation function. Specifically, it is necessary to solve n-number of equations, namely ##EQU1## Methods of indirect interpolation includes Lagrange interpolation, spline interpolation, etc. In Lagrange interpolation, m=n. In spline interpolation using a cubic polynomial, m=n+2. In this case, the number of equations is less than the number of unknowns, and therefore two end conditions such as a natural spline condition are introduced and m-number of parameters .phi..sub.i (i=1, 2, . . . , m) are determined. Next, P.sub.i is substituted into a function .PSI. decided by (.phi..sub.1, .phi..sub.2, . . . .phi..sub.m), and the interpolated value of point P.sub.i is found from EQU f(P.sub.i)=.PSI.(P.sub.i ; .phi..sub.1, .phi..sub.2, . . . .phi..sub.m)
When indirect interpolation is applied, an equation containing m-number of unknowns is solved. Therefore, in order to solve this equation, the number of arithmetic operations increases in proportion to m.sup.2, a prolonged computation time is required and computation efficiency declines.
Further, in a CAD program or the like, there are also cases where there is a limitation upon the maximum number of data points.
Moreover, since floating-point arithmetic is implemented when solving the equation, problems which arise are the effects of a rounding error as well as the need for a prolonged computation time.
When indirect interpolation is employed, unnatural oscillation is produced and there is a decline in interpolation accuracy. The reason for this is as follows: Since m-number of parameters .phi..sub.i (i=1,2, . . . , m) are decided based upon the data of an entire interpolation interval, influence is received from data points sufficiently remote from the interpolated point. Accordingly, if there is an interval in which data undergoes a sudden change, unnatural oscillation is produced. This is referred to as the "Runge phenomenon" in Lagrange interpolation and as the "Gibbs phenomenon" in interpolation using a Fourier series. With spline interpolation, a coefficient of an approximate polynomial is determined every interpolation interval, and hence there tends to be little influence from data points sufficiently remote from the interpolated point. However, in spline interpolation of degree n, continuity up to a derivative of degree (n-1) is introduced. Accordingly, the oscillation phenomenon propagates via the derivative. As a result, if there is an interval in which the derivative becomes large, oscillation occurs in the interpolation intervals before and after this interval and interpolation accuracy declines. This is as pointed out by Akima.
In order to prevent propagation of this oscillatory phenomenon, a rational spline interpolating method and the Akima method of interpolation have been proposed. Akima has proposed a method of determining polynomial coefficients locally. Effective results have been obtained even with regard to data in which oscillation is produced with ordinary spline interpolation. Experimental results show that when an interpolated value is decided using M items of data in the proximity of the interpolated point, rather than using all of the data at one time, interpolation accuracy is improved. It is necessary to experimentally determine the optimum value of the number M of data items for deciding the interpolated value. According to Akima, the gradient of the end points of the interpolation interval is determined by a proportional distribution of the gradient using four points at the periphery thereof, and the interpolated value is found by a cubic polynomial. As a result, the interpolated value is determined locally, propagation of oscillation is suppressed, and an excellent interpolated values are obtained.
However, with the Akima method of interpolation, floating point arithmetic is required and the interpolated value cannot be calculated at high speed.